{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Legal Binary Search Tree LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-search-tree #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉搜索树 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isValidBST"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #合法二叉搜索树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>实现一个函数，检查一棵二叉树是否为二叉搜索树。</p><strong>示例 1:</strong><pre><strong>输入:</strong><br>    2<br>   / &#92<br>  1   3<br><strong>输出:</strong> true<br></pre><strong>示例 2:</strong><pre><strong>输入:</strong><br>    5<br>   / &#92<br>  1   4<br>     / &#92<br>    3   6<br><strong>输出:</strong> false<br><strong>解释:</strong> 输入为: [5,1,4,null,null,3,6]。<br>     根节点的值为 5 ，但是其右子节点值为 4 。</pre>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [legal-binary-search-tree-lcci](https://leetcode.cn/problems/legal-binary-search-tree-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [legal-binary-search-tree-lcci](https://leetcode.cn/problems/legal-binary-search-tree-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self,root,min_,max_):\n",
    "        if not root:\n",
    "            return True\n",
    "        r = min_<root.val<max_\n",
    "        r = r and self.dfs(root.left,min_,root.val)\n",
    "        r = r and self.dfs(root.right,root.val,max_)\n",
    "        return r\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        return self.dfs(root,-100000000000000000,1000000000000000000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        def dfs(node, low, high):\n",
    "            if not node:\n",
    "                return True\n",
    "            \n",
    "            value = node.val\n",
    "            if value <= low or value >= high:\n",
    "                return False\n",
    "            \n",
    "            if not dfs(node.left, low, value):\n",
    "                return False\n",
    "            if not dfs(node.right, value, high):\n",
    "                return False\n",
    "            return True\n",
    "        \n",
    "        return dfs(root, float('-inf'), float('inf'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        def is_valid(n, lo, hi):\n",
    "            if n is None:\n",
    "                return True\n",
    "            if n.val <= lo or n.val >= hi:\n",
    "                return False\n",
    "            return is_valid(n.left, lo, n.val) and is_valid(n.right, n.val, hi)\n",
    "\n",
    "        return is_valid(root, float('-inf'), float('+inf'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode,left=-inf,right=inf) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        return left < root.val < right and self.isValidBST(root.left,left,root.val) and self.isValidBST(root.right,root.val,right)\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        def helper(node, lower = float('-inf'), upper = float('inf')) -> bool:\n",
    "            if not node:\n",
    "                return True\n",
    "            \n",
    "            val = node.val\n",
    "            if val <= lower or val >= upper:\n",
    "                return False\n",
    "\n",
    "            if not helper(node.right, val, upper):\n",
    "                return False\n",
    "            if not helper(node.left, lower, val):\n",
    "                return False\n",
    "            return True\n",
    "\n",
    "        return helper(root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        def check(root,maxvalue,minvalue):\n",
    "            if not root:\n",
    "                return True\n",
    "            if root.val<=minvalue or root.val>=maxvalue:\n",
    "                return False\n",
    "            return check(root.left,root.val,minvalue) and check(root.right,maxvalue,root.val)\n",
    "        return check(root,float('inf'),float('-inf'))\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:  \n",
    "    def isValidBST(self, root: TreeNode) -> bool:  \n",
    "        def checkBST(node: TreeNode, lower: float = -float('inf'), upper: float = float('inf')):  \n",
    "            if not node:  \n",
    "                return True  \n",
    "            if node.val <= lower or node.val >= upper:  \n",
    "                return False  \n",
    "            return checkBST(node.left, lower, node.val) and checkBST(node.right, node.val, upper)  \n",
    "          \n",
    "        return checkBST(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        def helper(node,lower = float('-inf'),upper = float('inf')):\n",
    "            if not node:\n",
    "                return True\n",
    "            val = node.val\n",
    "            if val <= lower or val >= upper:\n",
    "                return False\n",
    "            \n",
    "            if not helper(node.left,lower,val):\n",
    "                return False\n",
    "            if not helper(node.right,val,upper):\n",
    "                return False\n",
    "            return True\n",
    "        \n",
    "        return helper(root,lower = float('-inf'),upper = float('inf'))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "\n",
    "        stack, inorder = [], float('-inf')\n",
    "\n",
    "        while stack or root:\n",
    "            while root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            root = stack.pop()\n",
    "\n",
    "            if root.val <= inorder:\n",
    "                return False\n",
    "            inorder = root.val\n",
    "            root = root.right\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        stack, inorder = [], float('-inf')\n",
    "        while stack or root:\n",
    "            while root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            root = stack.pop()\n",
    "            if root.val <= inorder:\n",
    "                return False\n",
    "            inorder = root.val\n",
    "            root = root.right\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        \"\"\"判断中序遍历是否为递增序列\"\"\"\n",
    "        if not root:\n",
    "            return True \n",
    "        if not root.left and not root.right:\n",
    "            return True\n",
    "        preval = float(\"-inf\")\n",
    "        curr = root\n",
    "        stack = []\n",
    "        while curr or stack:\n",
    "            while curr:\n",
    "                stack.append(curr)\n",
    "                curr = curr.left\n",
    "            curr = stack.pop()\n",
    "            if curr.val <= preval:\n",
    "                return False\n",
    "            preval = curr.val\n",
    "            curr = curr.right\n",
    "        \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        return self.helper(root, -inf, inf)\n",
    "    \n",
    "    def helper(self, root, low, high):\n",
    "        if not root:\n",
    "            return True\n",
    "        if root.val <= low or root.val >= high:\n",
    "            return False\n",
    "        return self.helper(root.left, low, root.val) and self.helper(root.right, root.val, high)\n",
    "    \n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution(object):\n",
    "    def isValidBST(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        def valid(root,low,high):\n",
    "            if root==None: return True\n",
    "            if root.val<=low: return False\n",
    "            if root.val>=high: return False\n",
    "            return valid(root.left, low , root.val) and valid(root.right, root.val, high)\n",
    "        return valid(root, -float(\"inf\"), float(\"inf\"))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        def helper(low,high,root):\n",
    "            if not root:\n",
    "                return True\n",
    "            if root.val >= high or root.val <= low:\n",
    "                return False\n",
    "            return helper(low, root.val, root.left) and helper(root.val, high, root.right)\n",
    "        return helper(float(\"-inf\"), float(\"inf\"),root)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode,left=-inf,right=inf) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        return left < root.val < right and self.isValidBST(root.left,left,root.val) and self.isValidBST(root.right,root.val,right)\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        if root is None:\n",
    "            return True\n",
    "        stack, stack_index = [root], 0\n",
    "        left_visited = [False]\n",
    "        traversal = []\n",
    "        while stack_index >= 0:\n",
    "            if not left_visited[stack_index]:\n",
    "                left_visited[stack_index] = True\n",
    "                if stack[stack_index].left is not None:\n",
    "                    if stack_index + 1 >= len(stack):\n",
    "                        stack.append(stack[stack_index].left)\n",
    "                        left_visited.append(False)\n",
    "                    else:\n",
    "                        stack[stack_index + 1] = stack[stack_index].left\n",
    "                        left_visited[stack_index + 1] = False\n",
    "                    stack_index += 1\n",
    "            else:\n",
    "                traversal.append(stack[stack_index].val)\n",
    "                if stack[stack_index].right is not None:\n",
    "                    stack[stack_index] = stack[stack_index].right\n",
    "                    left_visited[stack_index] = False\n",
    "                else:\n",
    "                    stack_index -= 1\n",
    "        for i in range(len(traversal) - 1):\n",
    "            if traversal[i] >= traversal[i + 1]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode,left=float('-inf'),right=float('inf')) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        \n",
    "        val = root.val\n",
    "        return left<val<right and self.isValidBST(root.left,left,val) and self.isValidBST(root.right,val,right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "\n",
    "        stk = []\n",
    "        pre = None\n",
    "        cur = root\n",
    "\n",
    "        while stk or cur:\n",
    "            while cur:\n",
    "                stk.append(cur)\n",
    "                cur = cur.left\n",
    "            cur = stk.pop()\n",
    "            if pre and pre.val >= cur.val:\n",
    "                return False\n",
    "            pre = cur\n",
    "            cur = cur.right\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        \n",
    "        if not root:\n",
    "            return True\n",
    "        stack = []\n",
    "        pre = -inf\n",
    "        p = root\n",
    "        while len(stack) > 0 or p:\n",
    "            while p:\n",
    "                stack.append(p)\n",
    "                p = p.left\n",
    "            p = stack.pop()\n",
    "            if p.val <= pre:\n",
    "                return False\n",
    "            pre = p.val\n",
    "            p = p.right\n",
    "        \n",
    "        return True\n",
    "        \n",
    "    \n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: Optional[TreeNode], left=-inf, right=inf) -> bool:\n",
    "        if root is None:\n",
    "            return True\n",
    "        x = root.val\n",
    "        return left < x < right and \\\n",
    "               self.isValidBST(root.left, left, x) and \\\n",
    "               self.isValidBST(root.right, x, right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        if not root:    return True\n",
    "        def find(root, low, high):\n",
    "            if not root: return True\n",
    "            if root.left and root.left.val > root.val:    return False\n",
    "            if root.right and root.right.val < root.val:    return False\n",
    "\n",
    "            if not low < root.val < high: return False \n",
    "            if not find(root.left, low, min(high,root.val)):  return False\n",
    "            if not find(root.right, max(low, root.val), high):  return False\n",
    "\n",
    "            return True\n",
    "        return find(root, -float(\"inf\"), float(\"inf\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        def helper(node, lower = float('-inf'), upper = float('inf')) -> bool:\n",
    "            if not node:\n",
    "                return True\n",
    "            \n",
    "            val = node.val\n",
    "            if val <= lower or val >= upper:\n",
    "                return False\n",
    "\n",
    "            if not helper(node.right, val, upper):\n",
    "                return False\n",
    "            if not helper(node.left, lower, val):\n",
    "                return False\n",
    "            return True\n",
    "\n",
    "        return helper(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        def dfs(cur,mn,mx,flag):\n",
    "            if cur == None: return True\n",
    "            # print(cur.val,mn,mx)\n",
    "            if flag == None:\n",
    "                return dfs(cur.left,-1e20,mx,\"l\") & dfs(cur.right,mn,1e20,\"r\")\n",
    "            else:\n",
    "                if cur.val >= mx or cur.val <= mn: return False\n",
    "            lf = dfs(cur.left,mn,cur.val,\"l\")\n",
    "            rf = dfs(cur.right,cur.val,mx,\"r\")\n",
    "            return lf & rf\n",
    "\n",
    "        if not root: return True\n",
    "        return dfs(root,root.val,root.val,None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        self.res = True\n",
    "        def dfs(root,left_val, right_val):\n",
    "            if not self.res:\n",
    "                return\n",
    "            if root.left:\n",
    "                if root.left.val <= left_val or root.val <= root.left.val:\n",
    "                    self.res = False\n",
    "                dfs(root.left, left_val, root.val)\n",
    "            if root.right:\n",
    "                if root.right.val >= right_val or root.val >= root.right.val:\n",
    "                    self.res = False\n",
    "                dfs(root.right, root.val, right_val)\n",
    "        if root:\n",
    "            dfs(root, float('-inf'), float('inf'))\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        pre, cur = None, root\n",
    "        stack = []\n",
    "\n",
    "        while stack or cur:\n",
    "            while cur:\n",
    "                stack.append(cur)\n",
    "                cur = cur.left\n",
    "            cur = stack.pop()\n",
    "            if not pre:\n",
    "                pre = cur\n",
    "            else:\n",
    "                if cur.val <= pre.val:\n",
    "                    return False\n",
    "                pre = cur\n",
    "            cur = cur.right\n",
    "        return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        def func(root,lower,upper):\n",
    "            if not root:\n",
    "                return True\n",
    "            else:\n",
    "                if root.val<=lower or root.val>=upper:\n",
    "                    return False\n",
    "                else:\n",
    "                    if not func(root.left,lower,root.val):\n",
    "                        return False\n",
    "                    if not func(root.right,root.val,upper):\n",
    "                        return False\n",
    "                    return True\n",
    "        return func(root,-inf,inf)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        if not root:    return True\n",
    "        def find(root, low, high):\n",
    "            if not root: return True\n",
    "\n",
    "\n",
    "            if not low < root.val < high: return False \n",
    "            if not find(root.left, low, min(high,root.val)):  return False\n",
    "            if not find(root.right, max(low, root.val), high):  return False\n",
    "\n",
    "            return True\n",
    "        return find(root, -float(\"inf\"), float(\"inf\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution(object):\n",
    "    def isValidBST(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        def valid(root,mi,ma):\n",
    "            if root==None: return True\n",
    "            if root.val<=mi: return False\n",
    "            if root.val>=ma: return False\n",
    "            return valid(root.left, mi , root.val) and valid(root.right, root.val, ma)\n",
    "        return valid(root, -float(\"inf\"), float(\"inf\"))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        def dfs(cur, lower=float('-inf'),upper=float('inf')):\n",
    "            if not cur:return True\n",
    "            value = cur.val\n",
    "            if value<=lower or value>=upper:\n",
    "                return False \n",
    "            if not dfs(cur.left, lower, value):\n",
    "                return False\n",
    "            if not dfs(cur.right, value, upper):\n",
    "                return False\n",
    "            return True\n",
    "\n",
    "        return dfs(root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        return self.range_method(root)\n",
    "        # return self.order_method(root)\n",
    "\n",
    "    def range_method(self, root: TreeNode) -> bool:\n",
    "        return check_range(root, None, None)\n",
    "\n",
    "    def order_method(self, root: TreeNode) -> bool:\n",
    "        self.prev = -float(\"inf\")\n",
    "        return self.check_order(root)\n",
    "\n",
    "    def check_order(self, node: TreeNode) -> bool:\n",
    "        if node is None:\n",
    "            return True\n",
    "\n",
    "        if not self.check_order(node.left) or node.val < self.prev:\n",
    "            return False\n",
    "        self.prev = node.val\n",
    "        return self.check_order(node.right)\n",
    "\n",
    "\n",
    "def check_range(node: TreeNode, min_value: int | None, max_value: int | None) -> bool:\n",
    "    if node is None:\n",
    "        return True\n",
    "\n",
    "    value = node.val\n",
    "\n",
    "    if min_value is not None and value < min_value:\n",
    "        return False\n",
    "    if max_value is not None and value >= max_value:\n",
    "        return False\n",
    "\n",
    "    left_valid = check_range(node.left, min_value, value)\n",
    "    right_valid = check_range(node.right, value + 1, max_value)\n",
    "\n",
    "    return left_valid and right_valid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        # 中序遍历\n",
    "        pre = -math.inf\n",
    "        s, cur = [], root\n",
    "        while s or cur:\n",
    "            while cur:\n",
    "                s.append(cur)\n",
    "                cur = cur.left\n",
    "\n",
    "            cur = s.pop()\n",
    "            if cur.val <= pre:\n",
    "                return False\n",
    "            else:\n",
    "                pre = cur.val\n",
    "            cur = cur.right\n",
    "        return True\n",
    "\n",
    "\n",
    "        # 中序遍历\n",
    "        pre = -math.inf\n",
    "        def inorder(root):\n",
    "            if root:\n",
    "                if not inorder(root.left):\n",
    "                    return False\n",
    "\n",
    "                nonlocal pre\n",
    "                if root.val <= pre:\n",
    "                    return False\n",
    "                pre = root.val\n",
    "                \n",
    "                if not inorder(root.right):\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        return inorder(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "\n",
    "        def valid(node, min_v, max_v):\n",
    "            if not node:\n",
    "                return True\n",
    "\n",
    "            return min_v < node.val < max_v and valid(node.left, min_v, node.val) and valid(node.right, node.val, max_v)\n",
    "\n",
    "        \n",
    "        return valid(root, float(\"-inf\"), float(\"inf\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        def helper(node, lower = float('-inf'), upper = float('inf')) -> bool:\n",
    "            if not node:\n",
    "                return True\n",
    "            \n",
    "            val = node.val\n",
    "            if val <= lower or val >= upper:\n",
    "                return False\n",
    "\n",
    "            if not helper(node.right, val, upper):\n",
    "                return False\n",
    "            if not helper(node.left, lower, val):\n",
    "                return False\n",
    "            return True\n",
    "\n",
    "        return helper(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        def dfs(aRt, aMin, aMax):\n",
    "            #print(f\"dfs {aRt.val} {aMin} {aMax} vv {aMin and aRt.val <= aMin}\")\n",
    "            if aMin != None and aRt.val <= aMin or aMax != None and aRt.val >= aMax:\n",
    "                return False\n",
    "            else:\n",
    "                t = True\n",
    "                if aRt.left:\n",
    "                    t = t and dfs(aRt.left, aMin, aRt.val)\n",
    "                if t and aRt.right:\n",
    "                    t = t and dfs(aRt.right, aRt.val, aMax)\n",
    "                return t\n",
    "        if root:\n",
    "            return dfs(root, None, None)\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        return self.range_method(root)\n",
    "        # return self.order_method(root)\n",
    "\n",
    "    def range_method(self, root: TreeNode) -> bool:\n",
    "        return check_range(root, None, None)\n",
    "\n",
    "    def order_method(self, root: TreeNode) -> bool:\n",
    "        self.prev = -float(\"inf\")\n",
    "        return self.check_order(root)\n",
    "\n",
    "    def check_order(self, node: TreeNode) -> bool:\n",
    "        if node is None:\n",
    "            return True\n",
    "\n",
    "        if not self.check_order(node.left) or node.val < self.prev:\n",
    "            return False\n",
    "        self.prev = node.val\n",
    "        return self.check_order(node.right)\n",
    "\n",
    "\n",
    "def check_range(node: TreeNode, min_value: int | None, max_value: int | None) -> bool:\n",
    "    if node is None:\n",
    "        return True\n",
    "\n",
    "    value = node.val\n",
    "\n",
    "    if min_value is not None and value < min_value:\n",
    "        return False\n",
    "    if max_value is not None and value >= max_value:\n",
    "        return False\n",
    "\n",
    "    left_valid = check_range(node.left, min_value, value)\n",
    "    right_valid = check_range(node.right, value + 1, max_value)\n",
    "\n",
    "    return left_valid and right_valid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        stack=[]\n",
    "        res=[]\n",
    "        p=root\n",
    "        while p or stack:\n",
    "            while p:\n",
    "                stack.append(p)\n",
    "                p=p.left\n",
    "            node=stack.pop()\n",
    "            res.append(node.val)\n",
    "            p=node.right\n",
    "        return res==sorted(set(res))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        out=[]\n",
    "        def isValid(root):\n",
    "            if not root:\n",
    "                return \n",
    "\n",
    "            if isValid(root.left) is False:\n",
    "                return False\n",
    "\n",
    "            if not out :\n",
    "                out.append(root.val)\n",
    "            else:\n",
    "                if root.val>out[0]:\n",
    "                    out[0]=root.val\n",
    "                else:\n",
    "                    return False\n",
    "\n",
    "            if isValid(root.right) is False:\n",
    "                return False\n",
    "\n",
    "        if isValid(root) is False:\n",
    "            return False\n",
    "        else:\n",
    "            return True\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        stack = []\n",
    "        p = root\n",
    "        res = []\n",
    "\n",
    "        while p or stack :\n",
    "            while p:\n",
    "                stack.append(p)\n",
    "                p = p.left\n",
    "            \n",
    "            if stack :\n",
    "                node = stack.pop()\n",
    "                res.append(node.val)\n",
    "                p = node.right\n",
    "        \n",
    "        return res == sorted(set(res))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    pre = float('-inf')\n",
    "    res = True\n",
    "\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        self.inOrder(root)\n",
    "        return self.res\n",
    "\n",
    "    def inOrder(self, node):\n",
    "        if not node or not self.res:\n",
    "            return\n",
    "        self.inOrder(node.left)\n",
    "        cur = node.val\n",
    "        if cur <= self.pre:\n",
    "            self.res = False\n",
    "        self.pre = cur\n",
    "        \n",
    "        self.inOrder(node.right)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        pre=-inf\n",
    "        def inorder(root):\n",
    "            nonlocal pre\n",
    "            if not root:\n",
    "                return True\n",
    "            \n",
    "            if not inorder(root.left) or root.val<=pre:\n",
    "                return False\n",
    "            \n",
    "            pre=root.val\n",
    "\n",
    "            if not inorder(root.right):\n",
    "                return False\n",
    "            \n",
    "            return True\n",
    "        \n",
    "        return inorder(root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    pre = None\n",
    "    res = True\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        self.in_order(root)\n",
    "        return self.res\n",
    "\n",
    "    def in_order(self, root):\n",
    "        if not root or not self.res:\n",
    "            return\n",
    "       \n",
    "        self.in_order(root.left)\n",
    "        if not self.pre:\n",
    "            self.pre = root\n",
    "        else:\n",
    "            if self.pre.val >= root.val:\n",
    "                self.res = False\n",
    "                return\n",
    "            else:\n",
    "                self.pre = root\n",
    "        self.in_order(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        fa = -inf\n",
    "        while root:\n",
    "            if root.left:\n",
    "                pre = root.left\n",
    "                while pre.right is not None and pre.right != root:\n",
    "                    pre = pre.right\n",
    "                if pre.right is None:\n",
    "                    pre.right = root\n",
    "                    root = root.left\n",
    "                else:\n",
    "                    if root.val <= fa:\n",
    "                        return False\n",
    "                    fa = root.val\n",
    "                    pre.right = None\n",
    "                    root = root.right\n",
    "            else:\n",
    "                if root.val <= fa:\n",
    "                    return False\n",
    "                fa = root.val\n",
    "                root = root.right\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    # def isValidBST(self, root: TreeNode,left = -inf,right = inf) -> bool:\n",
    "    #     if not root:\n",
    "    #         return True\n",
    "\n",
    "    #     if (root.left != None and root.val <= root.left.val or root.right != None and root.val >= root.right.val ):\n",
    "    #         return False\n",
    "\n",
    "    #     x = root.val\n",
    "\n",
    "        \n",
    "    #     return left<x<right and self.isValidBST(root.left,left,x) and self.isValidBST(root.right,x,right)\n",
    "    def isValidBST(self, root: TreeNode):\n",
    "        if not root:\n",
    "            return True\n",
    "        # 中序遍历：左根右，如果有从小到大的有序数组，则是二叉搜索树\n",
    "        node_list = []\n",
    "        stack = []\n",
    "        node = root\n",
    "        while stack or node:\n",
    "            while node:\n",
    "                stack.append(node)\n",
    "                node = node.left\n",
    "            \n",
    "            if stack:\n",
    "                node = stack.pop()\n",
    "                node_list.append(node.val)\n",
    "                node = node.right\n",
    "        \n",
    "        return node_list == sorted(set(node_list))\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "import math\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        prev_val = -math.inf\n",
    "\n",
    "        def checkBst(node:TreeNode)->bool:\n",
    "            nonlocal prev_val\n",
    "            if node is None:\n",
    "                return True\n",
    "            left = checkBst(node.left)\n",
    "            if not left:\n",
    "                return False\n",
    "            if node.val<=prev_val:\n",
    "                return False\n",
    "            prev_val = node.val\n",
    "            right = checkBst(node.right)\n",
    "            return right\n",
    "        \n",
    "        return checkBst(root)\n",
    "            \n",
    "            \n",
    "        \n",
    "        checkBst(root,root.val)\n",
    "        return ans\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        prev = -2**33\n",
    "        res = True\n",
    "        def inOrderTraverse(node):\n",
    "            if node == None: return \n",
    "            inOrderTraverse(node.left)\n",
    "            nonlocal prev, res\n",
    "            if prev < node.val: prev = node.val\n",
    "            else: \n",
    "                res = False\n",
    "                return\n",
    "            inOrderTraverse(node.right)\n",
    "\n",
    "        inOrderTraverse(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        self.pre=float('-inf')\n",
    "        self.flag=True\n",
    "        def dfs(node):\n",
    "            if not node:return\n",
    "            dfs(node.left)\n",
    "            if node.val<=self.pre:\n",
    "                self.flag=False\n",
    "            self.pre=node.val\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "        return self.flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        # 中序遍历\n",
    "        pre = -math.inf\n",
    "        def inorder(root):\n",
    "            if root:\n",
    "                if not inorder(root.left):\n",
    "                    return False\n",
    "\n",
    "                nonlocal pre\n",
    "                if root.val <= pre:\n",
    "                    return False\n",
    "                pre = root.val\n",
    "                \n",
    "                if not inorder(root.right):\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        return inorder(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        if root == None:\n",
    "            return True\n",
    "        self.ans = True\n",
    "        self.temp = float('-inf')\n",
    "        def dfs(node):\n",
    "            if node == None:\n",
    "                return\n",
    "            if self.ans == False:\n",
    "                return\n",
    "            # if node.left == None and node.right == None:\n",
    "            #     if self.temp < node.val:\n",
    "            #         self.temp = node.val\n",
    "            #     else:\n",
    "            #         self.ans = False\n",
    "            #     return\n",
    "            dfs(node.left)\n",
    "            if self.ans:\n",
    "                if self.temp < node.val:\n",
    "                    self.temp = node.val\n",
    "                else:\n",
    "                    self.ans = False\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def process(self, head):\n",
    "        if not head:\n",
    "            return \n",
    "        self.process(head.left)\n",
    "        self.tmp.append(head.val)\n",
    "        self.process(head.right)\n",
    "\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        self.tmp = []\n",
    "        self.process(root)\n",
    "        print(self.tmp)\n",
    "\n",
    "        for i in range(len(self.tmp)):\n",
    "            if i > 0:\n",
    "                if self.tmp[i-1] >= self.tmp[i]:\n",
    "                    return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        pre = -inf\n",
    "        def handle(root):\n",
    "            nonlocal pre\n",
    "            if not root: return True\n",
    "            left = handle(root.left)\n",
    "            if pre < root.val:\n",
    "                pre = root.val\n",
    "            else:\n",
    "                return False\n",
    "            right = handle(root.right)\n",
    "            return left and right\n",
    "        return handle(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        self.after = -inf\n",
    "\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return True\n",
    "            t = True\n",
    "            t &= dfs(root.left)\n",
    "            t &= (root.val > self.after)\n",
    "            self.after = root.val\n",
    "            t &= dfs(root.right)\n",
    "\n",
    "            return t\n",
    "        return dfs(root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def process(self, head):\n",
    "        if not head:\n",
    "            return \n",
    "        self.process(head.left)\n",
    "        self.tmp.append(head.val)\n",
    "        self.k += 1\n",
    "        self.process(head.right)\n",
    "\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        self.tmp = []\n",
    "        self.k = 0\n",
    "        self.process(root)\n",
    "        print(self.tmp)\n",
    "\n",
    "        for i in range(self.k):\n",
    "            if i > 0:\n",
    "                if self.tmp[i-1] >= self.tmp[i]:\n",
    "                    return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    prev_val = -math.inf\n",
    "    marker = True\n",
    "\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "\n",
    "        self.mid_search(root)\n",
    "\n",
    "        return self.marker\n",
    "\n",
    "\n",
    "\n",
    "    def mid_search(self, node: TreeNode) -> None:\n",
    "\n",
    "        if node == None:\n",
    "\n",
    "            return\n",
    "        \n",
    "        # 中序遍历\n",
    "        self.mid_search(node.left)\n",
    "\n",
    "        if node.val <= self.prev_val:\n",
    "\n",
    "            self.marker = False\n",
    "\n",
    "            return\n",
    "\n",
    "        self.prev_val = node.val\n",
    "\n",
    "        self.mid_search((node.right))\n",
    "\n",
    "        return \n",
    "\n",
    "\n",
    "\n",
    "        # if root == None:\n",
    "        #     return True\n",
    "        \n",
    "        # if root.left !=None and root.left.val > root.val:\n",
    "        #     return False\n",
    "            \n",
    "        # if root.right !=None and root.right.val < root.val:\n",
    "        #     return False\n",
    "\n",
    "        # return self.isValidBST(root.left) and self.isValidBST(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    pre = -inf\n",
    "    def isValidBST(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root is None:\n",
    "            return True\n",
    "        if not self.isValidBST(root.left) or root.val <= self.pre:\n",
    "            return False\n",
    "        self.pre = root.val\n",
    "        return self.isValidBST(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def walk(self, root, res):\n",
    "        if root is None:\n",
    "            return\n",
    "        self.walk(root.left, res)\n",
    "        res.append(root.val)\n",
    "        self.walk(root.right, res)\n",
    "\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        res = []\n",
    "        self.walk(root, res)\n",
    "        for i in range(len(res)):\n",
    "            for j in range(i + 1, len(res)):\n",
    "                if res[i] >= res[j]:\n",
    "                    return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    pre = float('-inf')\n",
    "    res = True\n",
    "\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        self.inOrder(root)\n",
    "        return self.res\n",
    "\n",
    "    def inOrder(self, node):\n",
    "        if not node or not self.res:\n",
    "            return\n",
    "        self.inOrder(node.left)\n",
    "        cur = node.val\n",
    "        if cur <= self.pre:\n",
    "            self.res = False\n",
    "            return\n",
    "        self.pre = cur\n",
    "        \n",
    "        self.inOrder(node.right)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class SolutionNormal:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        def dfs(root, lower=float('-inf'), upper=float('inf')):\n",
    "            if not root:\n",
    "                return True\n",
    "            val = root.val\n",
    "            if val <= lower or val >= upper:\n",
    "                return False\n",
    "            if not dfs(root.left, lower, val):\n",
    "                return False\n",
    "            if not dfs(root.right, val, upper):\n",
    "                return False\n",
    "            return True\n",
    "        return dfs(root)\n",
    "        \n",
    "class Solution:\n",
    "    pre = float(\"-inf\")\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "            if not root:\n",
    "                return True\n",
    "            if not self.isValidBST(root.left) or root.val <= self.pre:\n",
    "                return False\n",
    "            self.pre = root.val\n",
    "\n",
    "            return self.isValidBST(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        inorder = []\n",
    "        self.inorderTrav(root, inorder)\n",
    "        for i in range(1, len(inorder)):\n",
    "            if inorder[i] <= inorder[i-1]:\n",
    "                return False \n",
    "            else:\n",
    "                continue \n",
    "        return True \n",
    "    \n",
    "    def inorderTrav(self, root: TreeNode, res: List) -> None:\n",
    "        if root is None:\n",
    "            return \n",
    "\n",
    "        self.inorderTrav(root.left, res)\n",
    "        res.append(root.val)\n",
    "        self.inorderTrav(root.right, res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    prev_val = -math.inf\n",
    "    marker = True\n",
    "\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "\n",
    "        self.mid_search(root)\n",
    "\n",
    "        return self.marker\n",
    "\n",
    "\n",
    "\n",
    "    def mid_search(self, node: TreeNode) -> None:\n",
    "\n",
    "        if node == None or self.marker==False:\n",
    "\n",
    "            return\n",
    "        \n",
    "        # 中序遍历\n",
    "        self.mid_search(node.left)\n",
    "\n",
    "\n",
    "        if node.val <= self.prev_val or self.marker==False:\n",
    "\n",
    "            self.marker = False\n",
    "\n",
    "            return\n",
    "\n",
    "        self.prev_val = node.val\n",
    "\n",
    "        self.mid_search(node.right)\n",
    "\n",
    "        return \n",
    "\n",
    "\n",
    "\n",
    "        # if root == None:\n",
    "        #     return True\n",
    "        \n",
    "        # if root.left !=None and root.left.val > root.val:\n",
    "        #     return False\n",
    "            \n",
    "        # if root.right !=None and root.right.val < root.val:\n",
    "        #     return False\n",
    "\n",
    "        # return self.isValidBST(root.left) and self.isValidBST(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    prev_val = -math.inf\n",
    "    marker = True\n",
    "\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "\n",
    "        self.mid_search(root)\n",
    "\n",
    "        return self.marker\n",
    "\n",
    "\n",
    "\n",
    "    def mid_search(self, node: TreeNode) -> None:\n",
    "\n",
    "        if node == None or not self.marker:\n",
    "\n",
    "            return\n",
    "        \n",
    "        # 中序遍历\n",
    "        self.mid_search(node.left)\n",
    "\n",
    "\n",
    "        if node.val <= self.prev_val:\n",
    "\n",
    "            self.marker = False\n",
    "\n",
    "            return\n",
    "\n",
    "        self.prev_val = node.val\n",
    "\n",
    "        self.mid_search(node.right)\n",
    "\n",
    "        return \n",
    "\n",
    "\n",
    "\n",
    "        # if root == None:\n",
    "        #     return True\n",
    "        \n",
    "        # if root.left !=None and root.left.val > root.val:\n",
    "        #     return False\n",
    "            \n",
    "        # if root.right !=None and root.right.val < root.val:\n",
    "        #     return False\n",
    "\n",
    "        # return self.isValidBST(root.left) and self.isValidBST(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        res = True\n",
    "\n",
    "        def traverse(root):\n",
    "            nonlocal res\n",
    "            if not root:\n",
    "                return -sys.maxsize,sys.maxsize\n",
    "        \n",
    "            left_max,left_min = traverse(root.left)\n",
    "            right_max,right_min = traverse(root.right)\n",
    "\n",
    "            if root.val>=right_min or root.val<=left_max:\n",
    "                res = False\n",
    "            \n",
    "            return max(root.val,right_max,left_max),min(root.val,right_min,left_min)\n",
    "        \n",
    "        traverse(root)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        def inorder(node, prev):\n",
    "            if node is None:\n",
    "                return True\n",
    "            if not inorder(node.left, prev):\n",
    "                return False\n",
    "            if node.val <= prev[0]:\n",
    "                return False\n",
    "            prev[0] = node.val\n",
    "            return inorder(node.right, prev)\n",
    "\n",
    "        prev = [float('-inf')]\n",
    "        return inorder(root, prev)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        global maxx\n",
    "        global minn\n",
    "        if not root:\n",
    "            maxx=-inf\n",
    "            minn=inf\n",
    "            return True\n",
    "        if not self.isValidBST(root.left):\n",
    "            return False\n",
    "        lmax = maxx\n",
    "        lmin = minn\n",
    "        if not self.isValidBST(root.right):\n",
    "            return False\n",
    "        rmax = maxx\n",
    "        rmin = minn\n",
    "        maxx = max(lmax, rmax, root.val)\n",
    "        minn = min(lmin, rmin, root.val)\n",
    "        return lmax < root.val and rmin > root.val\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        inorder = []\n",
    "        self.inorderTrav(root, inorder)\n",
    "        for i in range(1, len(inorder)):\n",
    "            if inorder[i] <= inorder[i-1]:\n",
    "                return False \n",
    "            else:\n",
    "                continue \n",
    "        return True \n",
    "    \n",
    "    def inorderTrav(self, root: TreeNode, res: List) -> None:\n",
    "        if root is None:\n",
    "            return \n",
    "\n",
    "        self.inorderTrav(root.left, res)\n",
    "        res.append(root.val)\n",
    "        self.inorderTrav(root.right, res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        result = True\n",
    "        last_val = -10000000000\n",
    "\n",
    "        def dfs(root):\n",
    "            nonlocal result, last_val\n",
    "\n",
    "            if not root or result == False:\n",
    "                return\n",
    "\n",
    "            dfs(root.left)\n",
    "            if root.val <= last_val:  # 二叉搜索树中序遍历，必然是一个单调递增数列\n",
    "                result = False\n",
    "                return\n",
    "            last_val = root.val\n",
    "            dfs(root.right)\n",
    "\n",
    "        dfs(root)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        def get_data(node):\n",
    "            if not node:\n",
    "                return True, None, None\n",
    "\n",
    "            left_ok, left_min, left_max = get_data(node.left)\n",
    "            right_ok, right_min, right_max = get_data(node.right)\n",
    "            \n",
    "            if not (left_ok and right_ok):\n",
    "                return False, None, None\n",
    "            \n",
    "            if left_max and left_max >= node.val or right_min and right_min <= node.val:\n",
    "                return False, None, None\n",
    "            \n",
    "            the_min = node.val if left_min is None else left_min\n",
    "            the_max = node.val if right_max is None else right_max\n",
    "            return True, the_min, the_max\n",
    "        \n",
    "        valid, _, _ = get_data(root)\n",
    "        return valid\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        inorder = []\n",
    "        self.inorderTrav(root, inorder)\n",
    "        for i in range(1, len(inorder)):\n",
    "            if inorder[i] <= inorder[i-1]:\n",
    "                return False \n",
    "            else:\n",
    "                continue \n",
    "        return True \n",
    "    \n",
    "    def inorderTrav(self, root: TreeNode, res: List) -> None:\n",
    "        if root is None:\n",
    "            return \n",
    "\n",
    "        self.inorderTrav(root.left, res)\n",
    "        res.append(root.val)\n",
    "        self.inorderTrav(root.right, res)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
